Nowadays, image search has become an indispensable feature of web search engines, including GOGGLE, YAHOO!, BING, and ASK. However, most of these image search engines are not effective enough because image signals are too complicated to handle. Due to the remarkable success of text retrieval for searching web pages, these search engines return images solely based on the surrounding text associated with such images on the web pages. So far, no visual cue or image content is used during such a search process.
Since text-based image search yields unsatisfactory search results due to the difficulty in automatically associating the visual content of images with descriptive text, the current practice instead relies on analyzing visual similarities among the images. This general area is referred to as Content-Based Image Retrieval (CBIR), which has been actively studied for the past two decades. The key component of current CBIR systems deals with computing pairwise visual similarities between images from which a global ordering is derived by way of well-established ranking methods such as PageRank (see Y. Jing and S. Baluja, “VisualRank: Applying PageRank to large-scale image search,” IEEE Transactions on Pattern Analysis and Machine Intelligence, volume 30, issue 11, pp. 1877-1890, 2008.) and Manifold Rank (see D. Zhou, J. Weston, A. Gretton, O. Bousquet, and B. Scholkopf, “Ranking on data manifolds,” in Advances in Neural Information Processing Systems (NIPS), volume 16, 2004.). Unfortunately, at the web scale that involves tens of thousands to millions of images, pairwise similarity computation becomes prohibitively expensive in terms of both computer memory and time costs.
Fast nearest neighbor search is increasingly vital to many large-scale tasks such as image search, and existing state-of-the-art search techniques mainly focus on how to approximate the search results achieved by the Euclidean distance. Given the fact that low-dimensional intrinsic manifolds can exist among a massive number of images, it is more effective to search images along the underlying manifold structures. The manifold ranking method provides ranking scores to all training samples with respect to a particular query by leveraging a neighborhood graph to reveal the data manifolds. However, such a method cannot scale up to very large databases where a rapid and accurate search engine is required.
There is, therefore, a need to develop an efficient and effective ranking method to handle large-scale image search.